package com.leetcode;

import java.util.HashSet;

/**
 * @className: Solution
 * @description: TODO 类描述
 * @author: YUANG
 * @date: 2022/1/19
 **/
public class ContainsNearbyDuplicate {
    public static void main(String[] args) {

        int[] arr = {1, 2, 5, 1};
        int k = 5;
        System.out.println(containsNearbyDuplicate(arr, k));
    }

    /**
     * 给你一个整数数组nums 和一个整数k ，判断数组中是否存在两个 不同的索引i和j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。
     *
     * @param nums
     * @param k
     * @return
     */
    public static boolean containsNearbyDuplicate(int[] nums, int k) {
        /**
         * 滑动窗口解法
         * 因为限制了  abs(i - j) <= k 所以有一个长度为K的窗口
         * 窗口开始放置在数组的头部,随着数组遍历向前移动
         */
        //创建窗口
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            //出现了重复的数字
            if (set.contains(nums[i])) {
                return true;
            }
            set.add(nums[i]);
            //将窗口前端的数字移除
            if (set.size() > k) {
                set.remove(nums[i - k]);
            }
        }
        return false;
    }
}
